import random
# import turtle
import copy
# import app.utils.sudoku as sdk
import time
import logging

start = time.time()
from fastapi import APIRouter


def get_next(m: "数独矩阵", x: "空白格行数", y: "空白格列数"):
    """ 功能：获得下一个空白格在数独中的坐标。
    """
    for next_y in range(y + 1, 9):  # 下一个空白格和当前格在一行的情况
        if m[x][next_y] == 0:
            return x, next_y
    for next_x in range(x + 1, 9):  # 下一个空白格和当前格不在一行的情况
        for next_y in range(0, 9):
            if m[next_x][next_y] == 0:
                return next_x, next_y
    return -1, -1  # 若不存在下一个空白格，则返回 -1，-1


def values(m: "数独矩阵", x: "空白格行数", y: "空白格列数"):
    """ 功能：返回符合"每个横排和竖排以及
              九宫格内无相同数字"这个条件的有效值。
    """
    i, j = x // 3, y // 3
    grid = [m[i * 3 + r][j * 3 + c] for r in range(3) for c in range(3)]
    v = set(range(1, 10)) - set(grid) - set(m[x]) - set(list(zip(*m))[y])
    v = random.sample(v, len(v))
    return v


def first_pos(m: "数独矩阵"):
    """ 功能：返回第一个空白格的位置坐标"""
    for x in range(9):
        for y in range(9):
            if m[x][y] == 0:
                return x, y
    return False, False  # 若数独已完成，则返回 False, False


def try_sudoku(m: "数独矩阵", x: "空白格行数", y: "空白格列数"):
    """ 功能：试着填写数独 """
    for v in values(m, x, y):
        m[x][y] = v
        next_x, next_y = get_next(m, x, y)
        if next_y == -1:  # 如果无下一个空白格
            return True
        else:
            end = try_sudoku(m, next_x, next_y)  # 递归
            if end:
                return True
            m[x][y] = 0  # 在递归的过程中，如果数独没有解开，则回溯到上一个空白格
    return False    # 在这一层没有解


def sudoku(m):
    x, y = first_pos(m)
    # logging.info(f'm:{m} x:{x} y:{y}')
    if try_sudoku(m, x, y):
        return True
    else:
        return False



def get_full_board(matrix, num_base, max_retries=5):
    retries = 0
    # logging.info(f'borad {matrix}')  
    while retries < max_retries:
        for loops in range(num_base):
            i, j = random.randint(0, 8), random.randint(0, 8)
            choices = values(matrix, i, j)
            if choices:
                matrix[i][j] = random.choice(choices)

        if sudoku(matrix):
            return True
        else:
            
            retries += 1
            print("尝试次数：", retries)
            logging.info(f'尝试次数 {retries}')
            # logging.info("尝试次数："+ retries)
    logging.info(f'res {retries}')     
    logging.info('生成终盘失败，请重新尝试')
    print("生成终盘失败，请重新尝试。")
    return False


def dig_holes(tries,board,answer):
    # 挖洞，每欲挖走一个，先测试除了原来数之外的其他数字是否能得到解
    for loops in range(tries):
        i, j = random.randint(0, 8), random.randint(0, 8)
        if board[i][j] == 0:
            continue
        possible = values(board, i, j)
        unique = True
        for num in possible:
            temp_board = copy.deepcopy(board)
            temp_board[i][j] = num
            if sudoku(temp_board):
                unique = False
                break
        if unique:
            answer[i][j] = board[i][j]
            board[i][j] = 0


def show_answer(x, y):
    if x > 220 and y < -220:
        show_sudoku(answer)

def print_sudoku_puzzle(matrix):
    # 将数独题目转换为二维数组形式
    sudoku_puzzle = []
    for row in matrix:
        row_output = []
        for val in row:
            if val != 0:
                row_output.append(val)
            else:
                row_output.append(0)  # 可以用其他符号表示空格
        sudoku_puzzle.append(row_output)
    return sudoku_puzzle
    
def print_sudoku_ans(matrix):
    # 将数独转换为二维数组形式
    sudoku_puzzle = []
    for row in matrix:
        row_output = []
        for val in row:
            if val != 0:
                row_output.append(val)
            else:
                row_output.append(0)  # 可以用其他符号表示空格
        sudoku_puzzle.append(row_output)
    return sudoku_puzzle



router = APIRouter()
@router.get('/getsudoku')
def getsudoku():
    # while True:
    #     if get_full_board(board, num_base=7):
    #         break
    board = [[0 for i in range(9)] for j in range(9)]
    answer = [[0 for i in range(9)] for j in range(9)]
    if not get_full_board(board, num_base=7, max_retries=5):
        logging.info('无法生成有效的数独终盘')
        return {"code": 500, "error": "无法生成有效的数独终盘"}
    # 打印终盘
    
    
    # for raw in board:
    #     print(raw)
    sudoku_ans = print_sudoku_ans(board)
    # 挖洞并打印数独题目
    dig_holes(88,board,answer)
    sudoku_puzzle = print_sudoku_puzzle(board)
    print("数独题目：")
    for row in sudoku_puzzle:
        print(row)

    level = 0
    for raw in range(9):
        for col in range(9):
            if board[raw][col] == 0:
                level += len(values(board, raw, col))
    print("难度系数：", level)

    # 记录生成数独盘所花的总时间
    end = time.time()
    print("花费时间：", end - start)

    return {
        'code':200,
        'puzzle': sudoku_puzzle,
        'answer': sudoku_ans,
    }



